#include <vector>
#include <string>

using namespace std;

class Solution {
private:
    static const int MAXSIZE = 100001;
    int father[MAXSIZE];
    int cols;
    int sets;

    int index(int a, int b) {
        return a * cols + b;
    }

    int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    void build(int n, int m, vector<vector<char>>& board) {
        cols = m;
        sets = 0;
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < m; b++) {
                if (board[a][b] == '1') {
                    int idx = index(a, b);
                    father[idx] = idx;
                    sets++;
                }
            }
        }
    }

    void unite(int a, int b, int c, int d) {
        int fx = find(index(a, b));
        int fy = find(index(c, d));
        if (fx != fy) {
            father[fx] = fy;
            sets--;
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }
        
        int n = grid.size();
        int m = grid[0].size();
        
        build(n, m, grid);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    if (j > 0 && grid[i][j - 1] == '1') {
                        unite(i, j, i, j - 1);
                    }
                    if (i > 0 && grid[i - 1][j] == '1') {
                        unite(i, j, i - 1, j);
                    }
                }
            }
        }
        
        return sets;
    }
};
